class TreeNode {
    constructor(data) {
        this.leftChild = null;
        this.rightChild = null;
        this.data = data;
    }
}

class BinaryTreeOrder {
    // 按中左右顺序创建
    createBinaryTree(inputList) {
        let node = null;
        if (inputList == null || !inputList.length) {
            return null;
        }
        let data = inputList.shift();
        if (data != null) {
            node = new TreeNode(data);
            node.leftChild = this.createBinaryTree(inputList);
            node.rightChild = this.createBinaryTree(inputList);
        }
        return node;
    }
    preOrderTraveralWithStack(treeNode){
        let stack = new Array();
        while (treeNode != null || stack.length) {
            while (treeNode != null){
                console.log(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            if (stack.length) {
                treeNode = stack.pop();
                treeNode = treeNode.rightChild;
            }
        }
    }
    // 前序遍历，递归，简单
    preOrderRecursion(treeNode) {
        if (treeNode === null) {
            return;
        }
        console.log(treeNode.data);
        this.preOrderRecursion(treeNode.leftChild); 
        this.preOrderRecursion(treeNode.rightChild); 
    }
    // 前序遍历，非递归：栈
    preOrderStack(treeNode) {
        let stack = new Array();
        while (treeNode !== null || stack.length > 0) {
            while (treeNode !== null) {
                console.log(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            treeNode = stack.pop();
            treeNode = treeNode.rightChild;
        }
    }
    // 中序遍历，递归，简单
    inOrderRecursion(treeNode) {
        if (treeNode === null) {
            return;
        }
        this.inOrderRecursion(treeNode.leftChild);
        console.log(treeNode.data);
        this.inOrderRecursion(treeNode.rightChild);
    }
    // 中序遍历，非递归：栈
    inOrderStack(treeNode) {
        let stack = new Array();
        while (treeNode !== null || stack.length > 0) {
            while (treeNode !== null) {
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            treeNode = stack.pop();
            console.log(treeNode.data);
            treeNode = treeNode.rightChild;
        }
    }
    // 后序遍历，递归
    postOrderRecursion(treeNode) {
        if (treeNode === null) {
            return;
        }
        this.postOrderRecursion(treeNode.leftChild);
        this.postOrderRecursion(treeNode.rightChild);
        console.log(treeNode.data);
    }
    // 后序遍历，非递归：栈
    postOrderStack(treeNode) {
        let stack = new Array();
        let last = null;
        while (treeNode !== null || stack.length > 0) {
            while (treeNode !== null) {
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            treeNode = stack[stack.length - 1];
            if (treeNode.rightChild && treeNode.rightChild !== last) {
                treeNode = treeNode.rightChild;
            } else {
                last = stack.pop();
                console.log(last.data);
                treeNode = null;
            }
        }
    }
    // 层序遍历，非递归：队列
    levelOrderQueue(treeNode) {
        let queue = new Array();
        queue.push(treeNode);
        while (queue.length > 0) {
            treeNode = queue.shift();
            console.log(treeNode.data);
            if (treeNode.leftChild !== null) {
                queue.push(treeNode.leftChild);
            }
            if (treeNode.rightChild !== null) {
                queue.push(treeNode.rightChild);
            }
        }
    }
    // 层序遍历，递归
    depth(treeNode) {
        if (treeNode === null) {
            return 0;
        }
        let l = this.depth(treeNode.leftChild);
        let r = this.depth(treeNode.rightChild);
        if (l >= r) {
            return l + 1;
        } else {
            return r + 1;
        }
    }
    _levelOrderRecursion(treeNode, level) {
        if (treeNode === null || level === 0) {
            return;
        }
        if (level === 1) {
            console.log(treeNode.data);
        }
        this._levelOrderRecursion(treeNode.leftChild, level - 1);
        this._levelOrderRecursion(treeNode.rightChild, level - 1);
    }
    levelOrderRecursion(treeNode) {
        if (treeNode === null) {
            return;
        }
        let depth = this.depth(treeNode);
        for (let i = 1; i <= depth; i++) {
            this._levelOrderRecursion(treeNode, i);
        }
    }
}

let binaryTreeOrder = new BinaryTreeOrder();
// let inputList = [3,2,9,null,null,10,null,null,8,null,4];
let inputList = [1,2,4,null,null,5,null,null,3,null,6,null,null]; // 一个按顺序的二叉树的数组结构
let treeNode = binaryTreeOrder.createBinaryTree(inputList);
// console.log(treeNode);
// binaryTreeOrder.preOrderTraveralWithStack(treeNode);

console.log('前序遍历，递归，难度简单');
binaryTreeOrder.preOrderRecursion(treeNode);
console.log('前序遍历，栈，难度中');
binaryTreeOrder.preOrderStack(treeNode);
console.log('中序遍历，递归，难度简单');
binaryTreeOrder.inOrderRecursion(treeNode);
console.log('中序遍历，栈，难度中');
binaryTreeOrder.inOrderStack(treeNode);
console.log('后序遍历，递归，难度简单');
binaryTreeOrder.postOrderRecursion(treeNode);
console.log('后序遍历，栈，难度难');
binaryTreeOrder.postOrderStack(treeNode);
console.log('层序遍历，队列，难度中');
binaryTreeOrder.levelOrderQueue(treeNode);
console.log('深度: ', binaryTreeOrder.depth(treeNode));
console.log('层序遍历，递归，难度难');
binaryTreeOrder.levelOrderRecursion(treeNode);
